package bTree.LeetCode;

public class 合并K个升序链表 {
    public ListNode mergeKLists(ListNode[] lists) {
        //串起来链表 O（n）
        ListNode head=null;
        ListNode tail = null;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) {
                continue;
            }else {
                if (null==head){
                    head=lists[i];
                }
            }

            ListNode pp = lists[i];
            while (null != pp.next) {
                pp = pp.next;
            }

            if (tail == null) {
                tail = pp;
            } else {
                tail.next = lists[i];
            }
            tail=pp;

        }
        return sortLists(head);
    }

    private ListNode sortLists(ListNode head) {
        if (null == head || null == head.next) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (null != slow && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode next = slow.next;
        slow.next = null;
        ListNode one = sortLists(head);
        ListNode two = sortLists(next);
        return mergeNode(one, two);
    }

    private ListNode mergeNode(ListNode one, ListNode two) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        ListNode p1 = one;
        ListNode p2 = two;
        while (null != p1 && null != p2) {
            if (p1.val > p2.val) {
                tail.next = p2;
                p2 = p2.next;
            } else {
                tail.next = p1;
                p1 = p1.next;
            }
            tail = tail.next;
        }
        if (null != p1) {
            tail.next = p1;
        } else if (null != p2) {
            tail.next = p2;
        }
        return dummy.next;
    }
}